FIG. 13 illustrates an LDPC encoding/decoding system. Reference numeral 101 denotes an encoder, 102 denotes a modulator, 103 denotes a channel, 104 denotes a demodulator, and 105 denotes a decoder. Prior to explanation of a conventional method of generating check matrixes for LDPC codes, encoding and decoding using LDPC codes are explained first.
At the sending side, the encoder 101 generates a check matrix H using a certain method. Then, a generator matrix G is derived from the following condition.
G: k×n matrix (where k is information-length and n is code-word length)
GHT=0 (where T is transposition)
The encoder 101 then receives a message (m1 m2 . . . mk) of an information-length k, and generates a code-word C using the generator matrix G as follows:
                                 C          =                    ⁢                                    (                                                m                  ⁢                  1                                ⁢                                                                  ⁢                                  m                  ⁢                  2                                ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                mk                            )                        ⁢                                                  ⁢            G                                                        =                    ⁢                                    (                                                c                  ⁢                  1                                ⁢                                                                  ⁢                                  c                  ⁢                  2                                ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                cn                            )                        ⁢                                                  ⁢                                          (                                                      where                    ⁢                                                                                  ⁢                                          H                      ⁡                                              (                                                                              c                            ⁢                            1                                                    ⁢                                                                                                          ⁢                                                      c                            ⁢                            2                                                    ⁢                                                                                                          ⁢                          …                          ⁢                                                                                                          ⁢                          cn                                                )                                                              ⁢                    T                                    =                  0                                )                            .                                          
The modulator 102 subjects the generated code-word C to digital modulation such as BPSK, QPSK or multi-valued QAM and transmits the resultant modulated signal.
At the receiving side, the demodulator 104 receives the modulated signal via the channel 103, and subjects it to a digital demodulation such as BPSK, QPSK or multi-valued QAM. The decoder 105 then subjects the LDPC-coded, demodulated result to an iterative decoding by “Sum-Product Algorithm” and provides an estimated result (corresponding to the original m1 m2 . . . mk).
Conventionally, check matrixes for the LDPC codes are generated as explained below. The check matrix proposed by Gallager, the proposer of the LDPC, is shown in FIG. 14, as an example.
This matrix is a binary matrix of “1” and “0”. Parts of “1” are hatched and parts of “0” are white. There are four “1”s in one row (hereinafter, “row weight”), and there are three “1”s in one column (hereinafter, “column weight”). All columns and rows have respective uniform weights. Thus, it is generally called “Regular-LDPC Code”. In the Gallager's codes, as shown in FIG. 14, the matrix is divided into three blocks, for example, and the second and third blocks are subjected to random permutation.
Because the random permutation has no certain rule, it is required to execute a time-consuming search by computer to find codes with a better characteristic.
Euclid geometric codes are such LDPC codes that exhibit a relatively stable and nice characteristic and can definitely generate a matrix without the use of the computer search. Y. Kou et al. (Y. Kou, S. Lin, and M. P. C. Fossorier, “Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery,” ISIT 2000, pp. 200, Sorrento, Italy, Jun. 25 to 30, 2000.) have proposed a method using such Euclid geometric codes. This method explains “Regular-LDPC Codes” consisting of regular ensembles.
A method of generating a check matrix for LDPC codes is herein proposed using Euclid geometric codes EG(2, 26) or a kind of finite geometric codes. This method achieves a characteristic that is located closely but 1.45 decibels away from the Shannon limit at an error rate of 10-4. FIG. 15 illustrates a configuration of Euclid geometric codes EG(2, 22), which has a structure of “Regular-LDPC Codes” with row and column weights of 4, 4.
Euclid geometric codes EG(m, 2s) have a characteristic defined as follows:
Code length:n = 22s − 1Redundant bit length:n − k = 3s − 1Information length:k = 22s − 3sMinimum distance:dmin = 2s + 1Density:r = 2s/(22s − 1).
As can be seen from FIG. 15, Euclid geometric codes have a structure with a cyclically sifted location of “1” in each row from an adjacent row. This structure can characteristically configure codes easily and definitely.
The check matrix generating method by Y. Kou et al. further includes changing row and column weights based on the Euclid geometric codes to extend rows and columns, if required. For example, when a column weight in EG(2, 22) is separated into halves, in the paper by Y. Kou et al., every other one of four weights located in one column is separated into two groups. FIG. 16 illustrates an exemplary regular separation of the column weight from 4 into 2.
On the other hand, Ludy et al. (M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation,” Proceedings of 1998 IEEE International Symposium on Information Theory, pp. 171, Cambridge, Mass., Aug. 16 to 21, 1998.) have reported that “Irregular-LDPC Codes” have a better characteristic than that of “Regular-LDPC Codes”. The “Irregular-LDPC Codes” represent such LDPC codes that have non-uniformity in either or both of row and column weights.
Richardson et al. (T. J. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 599 to 618, February 2001.) have analyzed it theoretically as well as Chung et al. (S.-Y. Chung, T. J. Richardson, and R. Urbanke, “Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation,” IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 657 to 670, February 2001.)
In particular, Chung et al. analyze a “Sum-Product Algorithm” for LDPC codes, on the assumption that a Log Likelihood Ratio (hereinafter, “LLR”) between an input and an output at an iterative decoder can be approximated in a Gaussian distribution, to derive a nice ensemble of row and column weights.
In the conventional method of generating check matrixes for LDPC codes by Chung et al., however, the number of “1” points in a row (corresponding to a degree distribution of variable nodes later described) and the number of “1” points in a column (corresponding to a degree distribution of check nodes later described) are both employed as variables to derive the degree distribution of variable nodes and the degree distribution of check nodes that can maximize the following equation (1) (rate: coding rate). In a word, a linear programming is employed to search an ensemble that minimizes a Signal to Noise Ratio (hereinafter, “SNR”).
                    rate        =                  1          -                                                    ∫                0                1                            ⁢                              ρ                ⁡                                  (                  x                  )                                                                                    ∫                0                1                            ⁢                              λ                ⁡                                  (                  x                  )                                                                                        (        1        )            
Therefore, a problem arises because a check matrix derived from the maximum of the “rate” has a flux and unstable characteristic. In addition, the conventional method of generating check matrixes for LDPC codes iteratively executes the derivation of the degree distribution of variable nodes and the derivation of the degree distribution of check nodes over certain times. Therefore, a problem arises because it takes time to some extent for searching.
It is an object of the present invention to solve at least the problems in the conventional technology.